package com.company.Sort2;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}15:48
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4,6,8,5,9};
//        int [] arr = {4,10,3,5,1,2};
//        heapify(arr,arr.length,0);
        heapSort(arr,arr.length);
        for (int i : arr){
            System.out.println(i);
        }
    }

    /**
     * n是长度
     * @param arr
     * @param n 数组的长度
     * @param i 输入点的坐标
     *          这是从头开始的
     */
    public static void heapify(int[] arr,int n,int i){//将树堆顶化
        if (i >= n){
            return;
        }
        int max = i;
        int temp = 0;
        int c1 = 2*i+1;
        int c2 = 2*i+2;
        if (c1 < n && arr[c1] > arr[max]){
            max = c1;
        }
        if (c2 < n && arr[c2] > arr[max]){
            max = c2;
        }
        if (max!=i){
            temp = arr[i];
            arr[i] = arr[max];
            arr[max] = temp;
            heapify(arr,n,max);//一直往下走
        }
    }

    public static void bulid_heap(int[] arr,int n){
        int last_node = n - 1;
        int parent = (last_node - 1) / 2;
        for (int i = parent; i >= 0; i--){
            heapify(arr,n,i);
        }
    }

    public static void heapSort(int[] arr,int n){
        bulid_heap(arr,n);
        for (int i = n - 1; i >= 0; i--){
            int temp = 0;
            temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr,i,0);
        }
    }

}
